package com.culture.bootdemo.算法;

/**
 * @Author: wen
 * @DateTime: 2024-12-05 16:03
 * @Description:
 **/
public class 反转链表 {


    //迭代方式：
    //使用三个指针: prev：指向当前节点的前一个节点。 current：指向当前节点。next：保存当前节点的下一个节点（防止链表断裂）。
    //遍历链表，逐一反转节点的指向。最终，prev指针指向反转后的链表头
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null; // 反转后链表的头
        ListNode current = head; // 当前处理的节点

        while (current != null) {
            ListNode next = current.next; // 保存下一个节点
            current.next = prev;         // 反转指针
            prev = current;              // 移动 prev 指针
            current = next;              // 移动 current 指针
        }

        return prev; // 返回反转后的链表头
    }

    //递归方式：
    public static ListNode reverseList2(ListNode head) {
        // 基础情况：空链表或只有一个节点时，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 递归反转后续链表
        ListNode reversed = reverseList2(head.next);
        // 调整当前节点的指向
        head.next.next = head; // 反转指针
        head.next = null;      // 将当前节点的 next 指针置为空
        return reversed;       // 返回反转后的链表头
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 反转链表
        ListNode reversed = reverseList(head);

        // 打印反转后的链表
        while (reversed != null) {
            System.out.print(reversed.val + " -> ");
            reversed = reversed.next;
        }
    }

}
